Алгоритм Кронекера

Дан многочлен $f(x) \in \mathbb{Z}[x]$, $\deg f = n > 1$. Необходимо найти многочлены $g(x)$ и $h(x)$ такие, что: $$f(x) = g(x)h(x)$$

Без ограничения общности будем искать $g(x)$ и $1 \leq \deg g \leq \left\lfloor \dfrac{n}{2} \right\rfloor$, $\deg g = m$. Будем делать перебор по $m$. Чтобы отгадать $g$, достаточно знать $g$ в $m + 1$ и воспользоваться интерполяционным многочленом Лагранжа. Возьмём какие-то точки $\{x_{i}\}$, например: $\{0, 1, \dots, m\}$ Так как $f(x_{i}) = g(x_{i})h(x_{i})$, то $g(x_{i}) \mid f(x_{i})$ в смысле делимости целых чисел. Набор $f(x_{0}), f(x_{1}), \dots, f(x_{m})$ содержит конечное число делителей, а значит, перебрав все делители, получим набор $g(x_{0}), g(x_{1}), \dots, g(x_{m})$. По полученным парам $\{(x_{i}, g(x_{i}))\}$ можно восстановить многочлен $g(x)$. Если полученный многочлен $g(x) \mid f(x)$, то $g(x)$ - искомый, алгоритм завершён. Иначе - продолжать перебор.